package day230511;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/5/11 17:54
 * 最长上升子序列
 */
public class Main02 {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            // 录入数据
            int n = scan.nextInt(); // 数据个数
            int[] sequence = new int[n]; // 录入序列
            for (int i = 0; i < sequence.length; i++) {
                sequence[i] = scan.nextInt();
            }
            // 使用动态规划解决 dp[i] 表示以 sequence[i] 结尾的最长上升子序列的长度
            int[] dp = new int[n];
            Arrays.fill(dp, 1); // 初始值均为1
            // 1 7 3 5 9 4 8
            // dp[0] 1 -> 1
            // dp[1] 1 7 -> 2
            // dp[2] 1 7 -> 2
            // dp[3] 1 3 5 -> 3 ...
            // dp[i] : max(dp[i], dp[j]+1)
            int result = 1; // 记录结果
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    if (sequence[i] > sequence[j]) {
                        // 与 i 位置的数比较, 如果更小, 则可以构成一个新的上升子序列 dp[j] + 1
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
                result = Math.max(result, dp[i]);
            }
            System.out.println(result);
        }
        scan.close();
    }
}
